#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// Fenwick（0-based），支持 update(pos, +1/-1) 以及 query(l,r)
struct Fenwick {
    int n;
    vector<int> f;
    Fenwick(int _n): n(_n), f(n+1,0) {}
    void update(int i, int v){
        for(++i; i<=n; i+=i&-i) f[i]+=v;
    }
    int query(int i) const {
        int s=0;
        for(++i; i>0; i-=i&-i) s+=f[i];
        return s;
    }
    int query(int l, int r) const {
        if(l>r) return 0;
        return query(r) - (l? query(l-1): 0);
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    string s;
    cin >> n >> s;

    // 映射 (->0, )->1
    vector<int> a(n);
    for(int i=0;i<n;i++) a[i] = (s[i]==')');

    // 1) 计算偶长“反转回文”半径 d2[i]
    //    中心取在 [0..n] 的缝隙上，第 i 个缝隙在字符 s[i-1] 和 s[i] 之间
    //    d2[i] = 最长 k， 使得对所有 0<=t<k, a[i-1-t] ^ a[i+t] == 1
    vector<int> d2(n+1,0);
    for(int i=0, l=0, r=-1; i<=n; i++){
        int k = 0;
        if(i <= r) 
            k = min(d2[l + r - i + 1], r - i + 1);
        // 尝试扩展
        while(i-1-k >= 0 && i+k < n && (a[i-1-k] ^ a[i+k]) == 1)
            k++;
        d2[i] = k;
        // 更新最远右端 r 对应的 i+k-1
        if(i + k - 1 > r){
            l = i - k;
            r = i + k - 1;
        }
    }

    // 2) 前缀和 P，让 '(' 为 +1, ')' 为 -1
    vector<ll> P(n+1,0);
    for(int i=1;i<=n;i++)
        P[i] = P[i-1] + (a[i-1]==0 ? +1 : -1);

    // 3) 单调栈求 nxt[pos] = 下一个 x>pos 且 P[x]<P[pos] 的位置（否则为 n+1）
    vector<int> nxt(n+1, n+1);
    {
        vector<int> stk;
        for(int i=0;i<=n;i++){
            while(!stk.empty() && P[i] < P[stk.back()]){
                nxt[stk.back()] = i;
                stk.pop_back();
            }
            stk.push_back(i);
        }
    }

    // 4) 预处理“到期删除”事件：当中心 i 前进到 nxt[pos] 时，就把 pos 从 Fenwick 剔除
    vector<vector<int>> remove_at(n+2);
    for(int pos=0; pos<=n-1; pos++){
        if(nxt[pos] <= n)
            remove_at[nxt[pos]].push_back(pos);
    }

    // 5) 初始化 Fenwick，pos=0..n-1 全部为 1
    Fenwick fw(n);
    for(int pos=0;pos<n;pos++)
        fw.update(pos, +1);

    ll ans = 0;
    // 扫描每个偶长回文中心 i=1..n-1
    // 对于中心 i，d2[i] 是最大 k，使得子串 [i-k...i+k-1] 满足反转回文
    // 子串前半段是 [i-k ... i-1]，合法性等价于
    //    nxt[i-k] > (i-1)
    for(int i=1;i<=n-1;i++){
        // 先删除所有到期 pos
        for(int pos: remove_at[i])
            fw.update(pos, -1);

        int k = d2[i];
        // Clamp k 以保证 i-k >= 0
        k = min(k, i);
        // 我们要统计所有 pos in [i-k .. i-1] 且 nxt[pos] > (i-1)
        // 剩在 Fenwick 里的 pos 一定满足 nxt[pos] >= i
        ans += fw.query(i-k, i-1);
    }

    cout << ans << "\n";
    return 0;
}
